package sort;

import java.util.Arrays;

public class RadixSort implements MySort {
    public static void main(String[] args) {
        int a[] = {8,9,1,7,2,3,5,4,6,0};
        //int a[] = {5,4};
        RadixSort radixSort = new RadixSort();
        radixSort.sort(a);
        System.out.println(Arrays.toString(a));
    }
    @Override
    public void sort(int[] a) {
        int[][] bucket = new int[10][a.length];
        int[] bCount = new int[10];
        int digit = 1;
        int max = a[0];
        int maxLength = 1;
        for(int k=0;k<maxLength;k++){
            for(int i = 0;i<a.length;i++){
                int index = Math.abs((a[i]/digit)%10);
                bucket[index][bCount[index]++] = a[i];
                if(Math.abs(a[i])>Math.abs(max)){
                    max = a[i];
                }
            }
            maxLength = (Math.abs(max)+"").length();
            int ii=0;
            for(int i=0; i<10; i++){
                if(bCount[i]>0){
                    for(int j=0;j<bCount[i];j++){
                        a[ii++] = bucket[i][j];
                    }
                    bCount[i]=0;
                }
            }
            digit*=10;
        }
    }
}
